#include "headfiles.h"

using namespace std;
int compareString(string &str1, string &str2) {
    if (str1.empty()) {
        if (str2.empty()) {
            return 0;
        }
        else {
            return -1;
        }
    }

    if (str2.empty()) {
        if (str1.empty()) {
            return 0;
        }
        else {
            return 1;
        }
    }

    size_t loc1 = str1.find(':');
    size_t loc2 = str2.find(':');
    string m1, m2;

    if (loc1 == string::npos) {
        m1.append(str1);
    }
    else {
        m1.append(str1, 0, loc1);
    }

    if (loc2 == string::npos) {
        m2.append(str2);
    }
    else {
        m2.append(str2, 0, loc2);
    }

    return m1.compare(m2);
}

void quickSortRecur(vector<string> &vec,
                     vector<string>::iterator start,
                     vector<string>::iterator end) {

    if (start >= end) {
        return;
    }

    vector<string>::iterator pivot_loc = start + ((end - start) / 2);
    string pivot = *pivot_loc;
    *pivot_loc = *start;

    vector<string>::iterator l, r, it;
    it = start;
    l = it + 1;
    r = end - 1;

    while (l <= r) {
        if (compareString(*l, pivot) <= 0) {
            *it = *l;
            ++it;
            ++l;
        }
        else {
            string tmp = *l;
            *l = *r;
            *r = tmp;
            r--;
        }
    }

    *it = pivot;

    quickSortRecur(vec, start, it);
    quickSortRecur(vec, it + 1, end);
}


static void sortInput(vector<string> &input) {
    quickSortRecur(input, input.begin(), input.end() - 1);
}

static string * findEntry(vector<string> &input, string *root) {
    vector<string>::iterator l, r, it;
    l = input.begin();
    r = input.end();
    --r;
    --r;

    while (l <= r) {
        it = l + (r - l) / 2;
        int res = compareString(*it, *root);
        if (res == 0) {
            return &(*it);
        }
        else if (res < 0) {
            l = it + 1;
        }
        else {
            r = it - 1;
        }
    }

    return NULL;
}

static bool traverseNeighbor(vector<string> &input, 
                             string *root, 
                             map<string, bool> &traversed, 
                             vector<string> &output) {
    if (root == NULL) {
        return false;
    }

    string *entry;
    string out_str;
    vector<string> traverse_list;
    entry = findEntry(input, root);
    if (entry == NULL) {
        return true;
    }
    else {
        cout << "entry = " << *entry << endl;
    }

    size_t pre_loc, loc;
    map<string, bool>::iterator it;
    loc = entry->find(':');

    // first charactor of the neighbor
    pre_loc = loc + 1;
    loc = entry->find(',', pre_loc);

    while (loc != string::npos) {
        string temp(*entry, pre_loc, loc - pre_loc);
        it = traversed.find(temp);
        if (it == traversed.end()) {
            out_str.append(temp);
            out_str.append(",");
            traversed.insert(pair<string, bool>(temp, true));
            traverse_list.push_back(temp);
        }

        pre_loc = loc + 1;
        loc = entry->find(',', pre_loc);
    }

    // last neighbor
    string temp(*entry, pre_loc);
    it = traversed.find(temp);
    if (it == traversed.end()) {
        out_str.append(temp);
        traversed.insert(pair<string, bool>(temp, true));
        traverse_list.push_back(temp);
    }
    output.push_back(out_str);

    vector<string>::iterator vit;
    for (vit = traverse_list.begin(); vit != traverse_list.end(); ++vit) {
        traverseNeighbor(input, &(*vit), traversed, output);
    }

    return true;
}

vector<string> traverseGraph(vector<string> input) {
    string *root = new string(*(input.end() - 1));

    sortInput(input);
    cout << "After sort" << endl;
    vector<string>::iterator tit;
    for (tit = input.begin(); tit != input.end(); tit++) {
        cout << *tit << endl;
    }
 
    vector<string> output;
    map<string, bool> neighbor_traversed;
    neighbor_traversed.insert(pair<string, bool>(*root, true));

    traverseNeighbor(input, root, neighbor_traversed, output);

    return output;
}


